Search results for " 05C12"
showing 3 items of 3 documents
A Note on Radio Antipodal Colouring of Paths
2005
International audience; The radio antipodal number of a graph G is the smallest integer c such that there exists an assignment f : V (G) -> {1, 2, . . . , c} satisfying |f(u) − f(v)| >= D − d(u, v) for every two distinct vertices u and v of G, where D is the diameter of G. In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin, and P. Zhang. Radio antipodal colorings of graphs, Math. Bohem. 127(1):57-69, 2002]. We also show the connections between this colouring and radio labelings.
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.
Packing colorings of subcubic outerplanar graphs
2018
Given a graph $G$ and a nondecreasing sequence $S=(s_1,\ldots,s_k)$ of positive integers, the mapping $c:V(G)\longrightarrow \{1,\ldots,k\}$ is called an $S$-packing coloring of $G$ if for any two distinct vertices $x$ and $y$ in $c^{-1}(i)$, the distance between $x$ and $y$ is greater than $s_i$. The smallest integer $k$ such that there exists a $(1,2,\ldots,k)$-packing coloring of a graph $G$ is called the packing chromatic number of $G$, denoted $\chi_{\rho}(G)$. The question of boundedness of the packing chromatic number in the class of subcubic (planar) graphs was investigated in several earlier papers; recently it was established that the invariant is unbounded in the class of all sub…